package com.bang.study.day01.list;

/**
 * @Auther: Bang
 * @Date: 2019/9/10 0010 09:01
 * @Description: 自定义链表
 */
public class LinkedList<E> {

    // 虚拟头节点
    private Node dummyHead;

    // 链表中元素个数
    private int size;


    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }


    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 在头结点添加元素
     * 时间复杂度: O(1)
     * @param e
     */
    public void addFirst(E e) {
        add(0, e);
    }
    /**
     * 在index处插入元素
     * 时间复杂度: O(n)
     * @param index
     * @param e
     */
    public void add(int index, E e) {
        if (index<0||index>size) {
            throw new IndexOutOfBoundsException("index Error");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    /**
     * 在链表尾添加元素
     * 时间复杂度: O(n)
     * @param e
     */
    public void addLast(E e) {
        add(size, e);
    }

    /**
     * 获取链表头元素
     * 时间复杂度: O(1)
     */
    public E getFirst() {
        if (isEmpty()) {
            throw new IllegalArgumentException("the linkedlist is empty");
        }
        Node first = dummyHead.next;
        return first.e;
    }

    /**
     * 获取index的元素
     * @param index
     * @return
     */
    public E get(int index) {
        if (isEmpty()) {
            throw new IllegalArgumentException("the linkedlist is empty");
        }
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current=current.next;
        }
        return current.e;
    }

    /**
     * 修改index的值为e
     * 时间复杂度 O(n)
     * @param index
     * @param e
     * @return
     */
    public void set(int index,E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index is out of bound");
        }
        Node current = dummyHead.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.e = e;
    }

    /**
     *  删除index处的元素
     *  时间复杂度 O(n)
     * @param index
     * @return
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index is out of bound");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node current = prev.next;
        E ret = current.e;
        prev.next = current.next;
        current.next = null;
        size--;
        return ret;
    }


    /**
     * 删除链接头元素
     * 时间复杂度 O(1)
     * @return
     */
    public E removeFirst() {
       return remove(0);
    }

    /**
     * 删除链接尾元素
     * 时间复杂度 O(n)
     * @return
     */
    public E removeLast() {
        return remove(size - 1);
    }



    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(get(i));
            if (i!=size){
                sb.append(",");
            }
        }
        sb.append("]");

        return "LinkedList{" +
                "ele=" + sb.toString() +
                ", size=" + size +
                '}';
    }

    /**
     * 链表中的节点 用于存储数据
     */
    private class Node{
        public E e;
        public Node next;

        public Node() {
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this.e = e;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e.toString() +
                    '}';
        }
    }


    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            list.addFirst(i);
            System.out.println(list);
        }
        list.set(0, 6666);
        System.out.println(list);
        System.out.println("-------------------------------");
       while (!list.isEmpty()){
           list.removeFirst();
           System.out.println(list);
       }


    }
}
